/* 

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

示例：

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

返回 3。和等于 8 的路径有:

1.  5 -> 3
2.  5 -> 2 -> 1
3.  -3 -> 11

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number}
 */
// 先序遍历+回溯
// 题解：https://leetcode-cn.com/problems/path-sum-iii/solution/437-lu-jing-zong-he-iii-xian-xu-bian-li-9do36/
var pathSum = function (root, sum) {
    // 二叉树-题目要求只能从父节点到子节点 所以用先序遍历

    // 路径总数
    let ans = 0

    // 存储前缀和
    let map = new Map()

    // 先序遍历二叉树
    function dfs(presum, node) {
        if (!node) return 0 // 遍历出口

        // 将当前前缀和添加到map
        map.set(presum, (map.get(presum) || 0) + 1)
        // 从根节点到当前节点的值
        let target = presum + node.val

        // target-sum = 需要的前缀和长度
        // 然而前缀和之前我们都存过了 检索map里key为该前缀和的value
        // map的值相当于有多少个节点到当前节点=sum 也就是有几条路径
        ans += (map.get(target - sum) || 0)

        // 按顺序遍历左右节点
        dfs(target, node.left)
        dfs(target, node.right)

        // 这层遍历完就把该层的前缀和去掉
        map.set(presum, map.get(presum) - 1)
    }
    dfs(0, root)
    return ans
};

// 双重递归
// 题解：https://leetcode-cn.com/problems/path-sum-iii/solution/shuang-zhong-di-gui-hao-yong-de-hen-by-xiao-jian-f/
var pathSum = function (root, sum) { //root为根节点， sum为规定的路径权值和
    if (!root) return 0 //若节点为空，返回0
    let sum1 = findDown(root, sum) //从根节点开始有多少满足条件的路径数，findDown函数是求从单个节点开始满足条件的路径数
    let sum2 = pathSum(root.left, sum) //遍历左子树求符合条件的路径数，
    let sum3 = pathSum(root.right, sum) //遍历右子树求符合条件的路径数
    return sum1 + sum2 + sum3; //得出总路径数
};

function findDown(root, sum) { // 求从单个节点开始满足条件的路径数，root为当前节点，sum为规定的路径权值和
    if (!root) return 0 //若节点为空，返回0
    let count = root.val === sum ? 1 : 0 // 当前节点权值刚好等于sum则算为1，否则为0
    let leftCount = findDown(root.left, sum - root.val) //剩下的权值要子树来凑，先看左子树能不能凑出来
    let rightCount = findDown(root.right, sum - root.val) //再看右子树是否能凑出来
    return count + leftCount + rightCount // 返回符合条件的路径数
}